/* insert sort */

#include <stdio.h>
#include <stdlib.h>

typedef int T;          /* type of item to be sorted */

#define compGT(a,b) (a > b)
#define ELEMENTS 5000


void insertSort(T *a, int lb, int ub) {
    T t;
    int i, j;

   /**************************
    *  sort array a[lb..ub]  *
    **************************/
    for (i = lb + 1; i <= ub; i++) {
        t = a[i];

        /* Shift elements down until */
        /* insertion point found.    */
        for (j = i-1; j >= lb && compGT(a[j], t); j--)
            a[j+1] = a[j];

        /* insert */
        a[j+1] = t;
    }
}

void GetData(T *a, int lb, int ub) 
{
    static FILE *infile;              /* input file */
    int i;
    
    infile = fopen("sortlist.dat", "r");
    if (infile == NULL) {
      printf("error: file sortlist.dat, unable to open\n");
      exit(1);
    }

    for (i=lb; i <= ub; i++) {
      if (fread(&a[i], sizeof(T), 1, infile) == 0) {
        break;
      }
    }

    fclose(infile);
    
    if (i <= (ub-lb)) {
      printf("error: file sortlist.dat, does not contain %d entries\n", ELEMENTS);
      exit(1);
    }
      
    
}

void PrintResult(T *a, int lb, int ub) 
{
    int i,flag;

    flag = 0;
    for (i=lb; i<ub; i++) {
	if (a[i+1]-a[i] < 0) {
		flag=1;
	}
    }

    if (flag) {
	printf("Sorry, the array was not sorted correctly\n");
    }
    else {
	printf("The array was sorted corectly!\n");
    }
}


int main() {
    int lb, ub;
    T *a;

    lb = 0; ub = ELEMENTS - 1;
    if ((a = malloc(ELEMENTS * sizeof(T))) == 0) {
        printf ("insufficient memory (a)\n");
        exit(1);
    }

    GetData(a, lb, ub);
    insertSort(a, lb, ub);
    PrintResult(a, lb, ub);
    
    return 0;
}
